package w4_c1_linkedlist;

import w3_c2_queue.LinkedListQueue;

/**
 * 递归实现链表的基本算法。
 * 核心是getParentNode方法。这个方法返回index节点的父节点。有了这个父节点，其他操作都很简单。
 * @param <E>
 */
public class LinkedListRecursive<E> {
    private class Node {
        E e;
        Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    Node head;
    int size;

    public LinkedListRecursive() {
        this.head = new Node(null, null);
        this.size = 0;
    }

    int getSize() {
        return size;
    }

    /**
     * 检查index是否合理。mode=0为插入模式，允许的下标范围为[0,size]
     * mode=1为删除模式，允许的下标范围为[0,size).
     * @param index
     * @param mode
     */
    void checkIndex(int index, int mode) {
        int range = size;
        if (mode == 0)//添加模式，允许的范围为[0,size].
            range = size;
        else  //删除模式，允许的范围为[0,size-1].
            range = size - 1;
        if (index < 0 || index > range)
            throw new IllegalArgumentException(String.format("Illegal index. Required: [%d,%d), " +
                    "got %d\n", 0, range, index));
    }

    /**
     * 向index处添加一个元素e。递归实现：思路是只向第一个位置（即index 0 处）添加节点。
     *
     * @param index
     * @param e
     */
    void add(int index, E e) {
        Node parent = getParentNode(index,0);
        parent.next = new Node(e, parent.next);
        size++;
    }

    /**
     * 向head表头（dummy表头）指向的链表的index位置处，添加元素e。递归实现。
     * 这是最初版本。写了getParentNode方法后，就不用这个实现了。
     *
     * @param head
     * @param index
     * @param e
     */
    @Deprecated
    void addHelper(Node head, int index, E e) {
        if (index == 0) {
            head.next = new Node(e, head.next);
            return;
        }
        addHelper(head.next, index - 1, e);
    }

    /**
     * 返回index节点的父节点
     *
     * @param index
     * @param mode
     * @return
     */
    Node getParentNode(int index,int mode) {
        checkIndex(index,mode);
        return getParentNodeHelper(head, index);
    }

    /**
     * 递归实现，基本情况定义为index=0的情况，直接返回head。
     *
     * @param head
     * @param index
     * @return
     */
    Node getParentNodeHelper(Node head, int index) {
        if (index == 0)
            return head;
        return getParentNodeHelper(head.next, index - 1);
    }

    /**
     * 返回index处节点值
     *
     * @param index
     * @return
     */
    public E get(int index) {
        Node parent = getParentNode(index, 1);
        return parent.next.e;
    }

    public E remove(int index) {
        Node parent = getParentNode(index, 1);
        Node res = parent.next;
        System.out.println(res);
        parent.next = res.next;
        size--;
        return res.e;

    }

    public void addFirst(E e) {
        add(0, e);
    }

    public void addLast(E e) {
        add(size, e);
    }

    /**
     * 是否包含元素e。基本情况定义为单个节点为空或其值为e。
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return containsHelper(head.next, e);
    }

    /**
     * contains递归实现体
     * @param head
     * @param e
     * @return
     */
    private boolean containsHelper(Node head, E e) {
       if(head == null)
           return false;
       if(head.e.equals(e))
           return true;
        return containsHelper(head.next, e);
    }

    public E getFirst() {
        return get(0);
    }

    public boolean isEmpty() {
        return size==0;
    }

    public void set(int index, E e) {
        Node parent = getParentNode(index, 0);
        parent.next.e = e;
    }

    /**
     * 返回值void版本的删除head中所有值为val的节点算法。
     * @param val
     */
    public void removeElements(E val) {
      removeElementsHelper(head,head.next,val);
    }

    /**
     * 删除从cur开始的头结点中，所有值为val的节点。cur为第一个实在节点，pre为cur的父节点。
     * 因为返回值是void，因此删除过程中需要父节点指针。
     * 递归出口为：当前节点为空；
     * 或者当前节点值为val时。此时，将父节点next指针指向cur.next，删去了cur节点。同时更新size。（这一点老是忘记）。
     * 调用函数的前提是，pre必须不为空。
     * @param pre
     * @param cur
     * @param val
     */
    private void removeElementsHelper(Node pre, Node cur, E val) {
        if(cur == null)
            return;
        if(cur.e.equals(val)){
            pre.next = cur.next;
            size--;
        }
        removeElementsHelper(cur,cur.next,val);
    }


    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        Node cur = head.next;
        res.append("Head: ");
        for (int i = 0; i < getSize(); i++) {
            res.append(cur.e + "->");
            cur = cur.next;
        }
        res.append("Null");
        return res.toString();
    }

    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        LinkedListRecursive<Integer> linkedListRecursive = new LinkedListRecursive<>();
        int i, n = 20;
        for (i = 0; i < n; i++) {
            linkedListRecursive.add(0, i);
            System.out.println(linkedListRecursive);
        }
        //contains test
        for (i = 0; i < 10; i++) {
            System.out.println("Contains test: " + (i+17) + ", res is : "+linkedListRecursive.contains(i+17));
        }

        //set test
        for (i = 0; i < 10; i++) {
            linkedListRecursive.set(i, i * i);
            System.out.printf("Set test: set index %d -> %d, res is: %s\n", i, i * i, linkedListRecursive);
        }

        //removeElements test。Refer to Leetcode 203.
        for(i=0;i<20;i++){
            linkedListRecursive.removeElements(i);
            System.out.printf("RemoveElements test: remove %d, res is: %s\n",i,linkedListRecursive);
        }
    }

}
